// Copyright 2012 Jay Young. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS-IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @fileoverview
 *
 * Test the LRU Cache implementation of rdoc/util/cache.
 */

var assert = require('assert'),
    Cache = require('rdoc/util/cache').Cache;


/**
 * Get a new Cache instance.  If the count parameter is given, the cache will
 * be filled with that number of key/value pairs of the form
 * ["k#", {"v#": true}].  Numbering will be such that k0 is the head key and
 * k(count - 1) is the tail key.
 *
 * @param {number=} cap The capacity to request.  Defaults to 5 if "count" is
 *    omitted.
 * @param {number=} count The number of items to add to the cache.  Must be less
 * than "cap".  If "cap" is omitted but "count" is not, cap will be count + 5.
 *
 * @return {{cache: Cache, values: [Object]}} A record containing the new
 *    cache and an array of the values.
 */
function getCache(cap, count) {
  if (count && cap && count > cap) {
    throw Error('Provided "count" must be lower than provided "cap".');
  }

  if (count && !cap) {
    cap = count + 5;
  }

  var cache = new Cache(cap || 5),
      values = []; // Array of cache values from head to tail

  if (count) {
    for (var i = 0; i < count; ++i) {
      var index = count - 1 - i,
          k = 'k' + index,
          vnum = 'v' + index,
          v = {};

      v[vnum] = true;
      values[index] = v;
      cache.set(k, v);
    }
  }

  assertListOrder(cache, values);
  
  return {
    cache: cache,
    values: values
  };
}


/**
 * Iterate through the linked list in the cache and assert that the order
 * of the values is the same as that of the given values list.  Also asserts
 * correct pointer references in the list entries.
 *
 * @param {Cache} cache The cache to test.
 * @param {Array.<*>} values The list of values.
 */
function assertListOrder(cache, values) {
  var head = cache.head_,
      tail = cache.tail_,
      size = cache.size_;

  if (size !== values.length) {
    assert.fail('# of values and cache size do not match: Size: ' + size +
                '; Values length: ' + values.length);
  }

  var entry = head, i = 0;
  if (! entry && size > 0) {
    assert.fail('No head found in cache.');
  }

  while (entry) {
    // Assert the value matches the expected entry in values.
    assert.equal(entry.value, values[i]);
    
    // Check list structure
    if (i === 0) {
      assert.isNull(entry.previous);
    }
    else {
      assert.equal(entry.previous.next, entry);
    }

    if (i < (size - 1)) {
      assert.equal(entry.next.previous, entry);
    }
    else {
      assert.isNull(entry.next);
      assert.equal(tail, entry);
    }

    ++i;
    entry = entry.next;
  }
  
  assert.equal(size, i);
}

exports['test Cache creation sets properties correctly'] = function() {
  var {cache, values} = getCache(2);

  // A new map was created with no keys.
  assert.equal(Object.keys(cache.map_).length, 0);
  
  // The head and tail pointers are null.
  assert.isNull(cache.head_);
  assert.isNull(cache.tail_);
  
  // Capacity and size were set properly.
  assert.equal(cache.capacity_, 2);
  assert.equal(cache.size_, 0);
  
  assertListOrder(cache, values);
};


exports['test Adding a value to an empty cache'] = function() {
  var {cache, values} = getCache(5),
      k = 'k0',
      v = {'v0': true};

  cache.set(k, v);

  assert.equal(cache.size_, 1);
  assert.deepEqual(cache.head_, {
    previous: null,
    next: null,
    value: v
  });

  assert.equal(cache.map_[k].value, v);
  assert.equal(Object.keys(cache.map_).length, 1);

  assert.equal(cache.tail_, cache.head_);

  var retrieved = cache.get(k);
  assert.equal(retrieved, v);

  assertListOrder(cache, [v]);
};


exports['test Retrieving a value from a size===1 cache'] = function() {
  var {cache, values} = getCache(5, 1),
      k = 'k0', // head
      v = values[0];

  assert.equal(cache.get(k), v);
  assert.equal(cache.map_[k].value, v);
  assert.isNull(cache.map_[k].previous);
  assert.isNull(cache.map_[k].next);

  assert.equal(cache.head_.value, v);
  assert.equal(cache.tail_.value, v);

  assert.equal(cache.head_, cache.tail_);
};


exports['test Adding a value to a size===1 cache'] = function() {
  var {cache, values} = getCache(5, 1),
      k0 = 'k0', // head
      v0 = values[0],

      k1 = 'k1',
      v1 = {'v1': true};

  cache.set(k1, v1);
  values.unshift(v1);

  assertListOrder(cache, values);
};


exports['test Retrieve head value from a size===2 cache'] = function() {
  var {cache, values} = getCache(5, 2),
      k0 = 'k0', // head
      v0 = values[0],

      k1 = 'k1', // tail
      v1 = values[1];

  var retrieved = cache.get(k0);
  assert.equal(retrieved, v0);

  assertListOrder(cache, values);
};


exports['test Retrieve tail value from a size===2 cache'] = function() {
  var {cache, values} = getCache(5, 2),
      k1 = 'k1', //tail
      v1 = values[1];

  var retrieved = cache.get(k1);
  assert.equal(retrieved, v1);
  
  assertListOrder(cache, [values[1], values[0]]);
};


exports['test Adding a value to a size===2 cache'] = function() {
  var {cache, values} = getCache(5, 2),
      kNew = 'kNew',
      vNew = {'vNew': true};

  cache.set(kNew, vNew);
  values.unshift(vNew);
  
  assertListOrder(cache, values);
};


exports['test Retrieve middle value from a size===3 cache'] = function() {
  var {cache, values} = getCache(5, 3),
      k1 = 'k1',
      v1 = values[1];

  var retrieved = cache.get(k1);
  assert.equal(retrieved, v1);
  
  assertListOrder(cache, [values[1], values[0], values[2]]);
};


exports['test Retrieve tail value from a size===3 cache'] = function() {
  var {cache, values} = getCache(5, 3),
      k2 = 'k2',
      v2 = values[2];

  var retrieved = cache.get(k2);
  assert.equal(retrieved, v2);
  
  assertListOrder(cache, [values[2], values[0], values[1]]);
};


exports['test Updating middle value in a size===3 cache'] = function() {
  var {cache, values} = getCache(5, 3),
      k1 = 'k1',
      v1 = {'vNew': true};

  var newValues = [v1, values[0], values[2]];

  cache.set(k1, v1);
  assertListOrder(cache, newValues);
};


exports['test Add beyond capacity'] = function() {
  var {cache, values} = getCache(4, 4),
      k = 'kNew',
      v = {'vNew': true};

  cache.set(k, v);
  values.pop();
  values.unshift(v);
  assertListOrder(cache, values);
};
